SRM 341

Match Summary

Round Overview
Discuss this match

In division 1, the easy problem was easier than usual, so most coders solved it quickly. In the coding phase, only ten coders found the solution to the hard problem, but nine of them failed the testing phase. The yellow coder, xhl_kogitsune, passed the systest and won the SRM for the first time.

In division 2, the hard problem was so tough that most coders failed to solve it. Only a new member, vanessa, managed to solve all 3 problems and won division.

ChangingString

Used as: Division Two - Level One:

This is just a greedy problem. Obviously, to gain the minimal possible target the distance between each letter in A, after changed, and the corresponding letter in B must be 0 (if they are different from each other) or 1 otherwise.

We choose K letters in A that have K maximal distance with K corresponding letters in B and change them in that way.

Java code follows:

1
2
3
4
5
6
7
8
9
10
public int distance(String A, String B, int K) {
  int n = A.length();
  int[] a = new int[n];
  for (int i = 0; i < n; i++) a[i] = Math.abs((int) A.charAt(i) - (int) B.charAt(i));
  Arrays.sort(a);
  int ans = 0;
  for (int i = 0; i < n - K; i++) ans += a[i];
  for (int i = n - K; i < n; i++) ans += a[i] == 0 ? 1 : 0;
  return ans;
}

KLastNonZeroDigits

Used as: Division Two - Level Two:

Used as: Division One - Level One:

This one was easier than the usual Div1 Easy or  Div2 Medium problem. Considering the small constraint of N, most coders were confident in solving this with the iterative approach.

Java code follows:

1
2
3
4
5
6
7
public String getKDigits(int N, int K) {
  long f = 1;
  for (long i = 1; i <= N; i++) f *= i;
  String s = String.valueOf(f);
  while (s.endsWith("0")) s = s.substring(0, s.length() - 1);
  return s.length() <= K ? s : s.substring(s.length() - K);
}

The problem will be a little tougher if the constraint of N is changed into 10^6.

LandAndSea

Used as: Division Two - Level Three:

Used as: Division One - Level Two:

| Value | 550 |
| Submission Rate | 250 / 544 (45.96%) |
| Success Rate | 73 / 250 (29.20%) |
| High Score | gozman for 359.52 points (23 mins 28 secs) |
| Average Score | 250.35 (for 73 correct submissions) |

The solution can be split into two parts - generating a tree with nodes considered as  islands and seas and finding the number of islands of each level. In generating a tree, we will add covering waters ‘.’ as the boundary of the map. We use the flood fill to find all seas and islands. The sea connected with the boundary element is defined as the root of the tree. From each visited sea we will visit unvisisted islands if they have at least one element vertically or horizontally adjacent to any element of the sea. From each visited island we will visit unvisisted seas if they have at least one element vertically, horizontally, or diagonally adjacent to any element of the island.

1
2
3
4
5
6
7
                    ...............000000000000000
                    xxx.x...xxxxx.xxx.x...xxxxx.011101000222220
                    xxxx....x...x.xxxx....x...x.011110000200020
                      ........x.x.x.........x.x.x.000000000203020. .xxxxx.x...x...xxxxx.x...x.000444440200020. .x...x.xxx.x - > ...x...x.xxx.x. - > 000466640222020. .x.x.x...x.....x.x.x...x...000467640002000. .x...x...xxx...x...x...xxx.000466640002220
                      ...xxxxxx........xxxxxx.....000044444400000
                    x.............x.............050000000000000
                      ...............000000000000000

In the picture above, connected groups 0 and 6 are seas and connected groups are islands. The root 0 has children 1, 2, 3, 4, 5. The node 4 has a child 6(a sea). The sea 6 has a child 7(an island).

After creating the tree, it is easy to find the number of islands of each level as following. Any island or sea that have no child will be defined as level 1 and 0, respectively. The level of each island is defined as the maximum level of all its own children plus 1 and the level of each sea is defined as the maximum level of all its own children.

See the kalinov’ solution for an implementation of this approach.

See also Vasyl(alphacom)’ solution  for a nice recursive approach.

ValidPlates

Used as: Division One - Level Three:

If the plates stayed reasonably short, this is a straightforward dynamic programming problem. The example with the very long plate should indicate that a bit more is required, however. Specifically, if we attempt a dynamic programming approach, with our state being the length of the plate and the first character in the plate, and our value being the count of plates with those characteristics, our runtime would be O(length*digits^2) which is too high. Nonetheless it is instructive to examine the dynamic programming solution and see how we can improve it.

The dynamic programming solution is straightforward. Expressed as a recursion, we have:

1
2
3
4
5
6
7
8
9
10
11
long count(int len, char firstdigit) {
  if (len == 1)
    return 1;
  else {
    long r = 0;
    for (char d: digits)
      if (legal[firstdigit][d])
        r += count(len - 1, d);
    return r;
  }
}

Like many dynamic programming problems of this sort, the code above is essentially matrix multiplication, with the condition on legal replaced by multiplication by an entry in a matrix that is either 0 or 1. That is, the above code can be rewritten to compute all the digits in parallel using the following code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long[][] counts(int len) {
  if (len == 1)
    return new long[][] {
      {
        1
      }, {
        1
      }, {
        1
      }, {
        1
      }, ..., {
        1
      }
    };
  else
    return matrixmul(legal, counts(len - 1));
}

where legal is a 0/1 matrix representing the legal sets of digits. Since we’re just using matrix multiplication, we can of course convert this to a simple matrix exponentiation routine that will give us the counts at any length very quickly.

We need to avoid iterating over the possible lengths, however, since the final length can be quite high. We’d rather use a binary search. But our count vector contains only the values at a particular length. One way to solve this issue is to introduce an eleventh digit, lexicographically before all the others; we’ll use ‘X’ here. Then, when considering the length three plates, for instance, all length two plates will be included, but preceded by ‘X’. Similarly, all length one plates will be included, preceded by two 'X’s. If we do this, one computation will tell us the total number of plates of a given length and smaller. We have to extend our “legal” matrix with an eleventh row and column; we do not permit ‘X’ to come after anything but another ‘X’, and we never allow an ‘X’ to precede a ‘0’.

With this improvement, we can use binary search to calculate the length. When computing the count matrix at a length len, if the number of plates starting with ‘X’ is greater than our sequence number, we know we’re too high. If the sum of plates at that length is greater than our sequence number, we’re at the correct length. Otherwise we’re too low.

Once we have the length, we can compute the digits one by one by simply iterating over the potential starting digits, determine the starting sequence of the plate with each starting digit by accumulating values from the matrix, and figuring out where our sequence number fits. Then we can subtract the count of plates with all prior digits from our sequence number, and move on to the next digit.